package com.explorati.LeetCode100.SameTree;

/**
 * 100.SameTree 两个数是否相同
 * 
 * Given two binary trees, write a function to check if they are the same or
 * not.
 * 
 * Two binary trees are considered the same if they are structurally identical
 * 
 * @author explorati
 *
 */
public class Solution {

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public static boolean isSameTree(TreeNode p, TreeNode q) {
		boolean flag = true;
		// 首先判断是否为空，都为空返回true，说明为null的节点相同
		if (p == null && q == null) {
			return true;
			// 若有一个不为空，则返回false，说明其中一个的深度深一点
		} else if (p == null && q != null) {
			return false;
		} else if (p != null && q == null) {
			return false;
		}
		// 接收flag并判断
		boolean flag1 = isSameTree(p.left, q.left);
		boolean flag2 = isSameTree(p.right, q.right);
		if (flag1 == false || flag2 == false) {
			return false;
		}

		// 判断完左右节点之后，在返回本节点的比较值
		return p.val == q.val;
	}

	public static void main(String[] args) {
		Solution s = new Solution();
		TreeNode root = s.new TreeNode(1);
		root.left = s.new TreeNode(2);
		root.right = s.new TreeNode(3);
		root.left.left = s.new TreeNode(4);
		root.right.left = s.new TreeNode(5);

		TreeNode root1 = s.new TreeNode(1);
		root1.left = s.new TreeNode(2);
		root1.right = s.new TreeNode(3);
		root1.left.left = s.new TreeNode(4);
		root1.right.left = s.new TreeNode(5);

		boolean flag = isSameTree(root, root1);
		System.out.println(flag);
	}
}
